PathSum Problems

问题描述（难度简单-112/113/437）

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

[
   [5,4,11,2],
   [5,8,4,5]
]

P112

Using Recursive

package P112;

import P104.TreeNode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left==null && root.right==null && root.val==sum) {
            return true;
        }
        boolean left=hasPathSum(root.left,sum-root.val);
        boolean right=hasPathSum(root.right,sum-root.val);

        return left || right;
    }
}

P113

Using Recursive

package P113;

import P104.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root,int sum){
        List<List<Integer>> result=findPathSum(root,sum);
        result.forEach(integers -> {
            int i=0,j=integers.size()-1;
            while (i<j){
                Integer temp=integers.get(i);
                integers.set(i,integers.get(j));
                integers.set(j,temp);
                i++;j--;
            }
        });
        return result;
    }
    public List<List<Integer>> findPathSum(TreeNode root, int sum) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> result=new ArrayList<>();
        if (root.left==null && root.right==null && root.val==sum) {
            List<Integer> list=new ArrayList<>();
            list.add(root.val);
            result.add(list);
            return result;
        }
        List<List<Integer>> leftResult=findPathSum(root.left,sum-root.val);
        List<List<Integer>> rightResult=findPathSum(root.right,sum-root.val);

        rightResult.forEach(integers -> integers.add(root.val));
        leftResult.stream().forEach(integers -> {
            integers.add(root.val);
            rightResult.add(integers);
        });

        return rightResult;

    }
}

Using Recursive+LinkedList

每次递归出来数组无法指定插入位置（数组不利于插入），换成链表，避免了重新换位置。

package P113;

import P104.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 直接使用linkedList便于插入，不需要重新排序
 * @autor yeqiaozhu.
 * @date 2019-10-17
 */
public class UsingLinkedList {

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) {
            return new LinkedList<>();
        }
        List<List<Integer>> result=new ArrayList<>();
        if (root.left==null && root.right==null && root.val==sum) {
            List<Integer> list=new LinkedList<>();
            list.add(root.val);
            result.add(list);
            return result;
        }
        List<List<Integer>> leftResult=pathSum(root.left,sum-root.val);
        List<List<Integer>> rightResult=pathSum(root.right,sum-root.val);

        rightResult.forEach(integers -> integers.add(0,root.val));
        leftResult.stream().forEach(integers -> {
            integers.add(0,root.val);
            rightResult.add(integers);
        });
        return rightResult;
    }
}

P437

类比上面两题虽然这道标记为简单，但是感觉理解和逻辑上难度更大。

Using Recursive

对于递归问题我们首先要明确我们需要解决的问题，这里需要解决的问题是，二叉树中有几个和为指定sum的组合。我们的输入是root和sum，输出是组合数量。然后我们尝试将这个问题分解为子问题，要找到任意节点为根，和为sum的所有可能。所以第一个递归是遍历以每个节点为根的和为sum的数量，第二个递归是根为特定节点的和为sum的数量。

• 明确需要解决的问题。函数的输入输出可递归分解为子问题。
• 构造出递归的基本结构。

package P437;

import CommonUtils.TreeNodeUtils;
import P104.TreeNode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        //以当前root节点开头的 统计
        int mid=count(root,sum);
        int left=pathSum(root.left,sum);
        int right=pathSum(root.right,sum);

        return mid+left+right;
    }
    public int count(TreeNode root,int sum){
        if (root == null) {
            return 0;
        }
        int isMe=(root.val==sum)?1:0;
        int countLeft=count(root.left,sum-root.val);
        int countRight=count(root.right,sum-root.val);

        return isMe+countLeft+countRight;
    }
    public static void main(String[] args) {
        int[] ints={10,5,-3,3,2,11,3,-2,1};
        TreeNode treeNode=TreeNodeUtils.buildTreeNodeUsingArray(ints);

        new Solution().pathSum(treeNode,8);
    }
}

总结

在写递归的过程中首先参考递归的书写范式，逆向考虑递归要跟踪调用栈实际上非常复杂。